//	ID : pallab81
// 	PROG : 10852
// 	LANG : C++
// 	2011-07-06-14.27.38 Wednesday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
int t_prime;
int primes[10010];

inline void sieve(){
    int good[10010],i,j;
    memset( good, -1, sizeof(good) );
    int sqrtN = (int)sqrt( (double)10010 );

    for(i=3;i<=sqrtN;i+=2){
        if( good[i]!=0 ){
            for(j=i*i; j<10010; j+=i){
                good[j]=0;
            }
        }
    }
    primes[0]=2;
    t_prime=1;
    for(j=3;j<=10000; j+=2){
        if( good[j]!=0 ){
            primes[t_prime]=j;
            ++t_prime;
        }
    }
}

inline void doit(){
    int n,i,j;
    scanf("%d",&n);
    int res=-1;
    int dif=-1;
    for(i=0;i<t_prime;++i){
        if( primes[i]>n)break;
        int pivot = n/primes[i] ;
        int lo = pivot*primes[i];
        int hi = (pivot+1)*primes[i];
        if( lo <= n && hi>n ){
            if( n >= lo ){
                if( n-lo >dif ){
                    res = primes[i];
                    dif = n-lo;
                }
            }
        }
    }
    printf("%d\n",res);
}

int cases;
int main(){
    sieve();
    scanf("%d",&cases);
    while(cases--){
        doit();
    }

return 0;
}

